package com.leetcode.algorithm.y18.m05;

/**
 * leetcode-cn.com
 * 172. 阶乘后的零
 * 189. 旋转数组
 * 190. 颠倒二进制位
 * 191. 位1的个数
 * @author: jie.deng
 * @time: 2018年5月9日 上午9:24:04
 */
public class MySolution0509 {

	/**
	 * 172. 阶乘后的零 
	 * 给定一个整数 n，返回 n! 结果尾数中零的数量。
	 * 
	 * 示例 1:
	 * 输入: 3 
	 * 输出: 0 
	 * 解释: 3! = 6, 尾数中没有零。 
	 * 
	 * 示例 2:
	 * 输入: 5 
	 * 输出: 1 
	 * 解释: 5! = 120, 尾数中有 1 个零. 
	 * 
	 * 说明: 你算法的时间复杂度应为 O(logN) 。
	 * 
	 * @param n
	 * @return
	 */
    public int trailingZeroes(int n) {
    	//5,15,25,35... n/5
    	//25,75...
    	//125...
    	//625...
    	//...
    	//10,20,..100.. n/10
    	//100,200...
    	//1000...
    	//...
    	
    	//改进思路
    	//5,10,15,... n/5
    	//25,50,75,... n/5
    	//125,250,... n/25
    	//...
		int count = 0;
		int i5 = 1;
		//while (i5 * 5 <= n/5) {	//这里i5 * 5会导致int移除
		while (i5 <= n/5) {	
			i5 = i5 * 5;
			count += n / i5;
		}
		return count;
    }
    
    /**
	 * 189. 旋转数组 
	 * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
	 * 
	 * 示例 1:
	 * 输入: [1,2,3,4,5,6,7] 和 k = 3 
	 * 输出: [5,6,7,1,2,3,4] 
	 * 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 
	 * 向右旋转 2 步: [6,7,1,2,3,4,5] 
	 * 向右旋转 3 步: [5,6,7,1,2,3,4] 
	 * 
	 * 示例 2:
	 * 输入: [-1,-100,3,99] 和 k = 2 
	 * 输出: [3,99,-1,-100] 
	 * 解释: 向右旋转 1 步: [99,-1,-100,3] 
	 * 向右旋转 2 步: [3,99,-1,-100] 
	 * 
	 * 说明:
	 * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 
	 * 要求使用空间复杂度为 O(1) 的原地算法。
	 * 
	 * @param nums
	 * @param k
	 */
    public void rotate(int[] nums, int k) {
    	int len = nums.length;
		if (len == 0) {
			return ;
		}
        k = k % len;
        //第1种方法.每次移动一个位置，索引从nums.length-1-1到0，移动k次
//		while (k > 0) {
//			int tailIdx = nums.length - 1;
//			int tmp = nums[tailIdx];
//			while (tailIdx >= 1) {
//				nums[tailIdx] = nums[tailIdx - 1];
//				tailIdx -= 1;
//			}
//			nums[0] = tmp;
//			k--;
//		}
        
        //第2种方法.每次移动k个位置，
		//先移动索引为nums.length-1,nums.length-1-k,...
		//第二轮nums.length-2,nums.length-2-k...
		//...
		//最后一轮nums.length-k,然后nums.length-k-k,...
		int[] tail = new int[k];
		for (int i = 1; i <= k; i++) {
			int j = len - i;
			int tmp = nums[j];
			while (j >= k) {
				nums[j] = nums[j - k];
				j -= k;
			}
			tail[k - i] = tmp;
		}
		for (int i = 0; i < k; i++) {
			nums[i] = tail[i];
		}
		
		
		//第3种方法.倒置
		//第1步:倒置整个数组
		//第2步:倒置数组前k个元素
		//第3步:倒置数组索引范围为[k+1,len-1]的元素
    }
    
    
    /**
	 * 190. 颠倒二进制位 
	 * 颠倒给定的 32 位无符号整数的二进制位。
	 * 
	 * 示例:
	 * 输入: 43261596 
	 * 输出: 964176192 
	 * 解释: 43261596 的二进制表示形式为  00000010100101000001111010011100 ， 
	 * 返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。 
	 * 
	 * 进阶: 
	 * 如果多次调用这个函数，你将如何优化你的算法？
	 * 
	 * @param n
	 * @return
	 */
	public int reverseBits(int n) {
//		String str = Integer.toBinaryString(n);
//		int len = str.length();
//		char[] chars = new char[32];
//		Arrays.fill(chars, '0');
//		System.arraycopy(str.toCharArray(), 0, chars, 32 - len, len);
//		for (int i = 0; i < 16; i++) { // i=[0,15] 与 [31,16]交换
//			chars[i] = (char) (chars[i] ^ chars[31 - i]);
//			chars[31 - i] = (char) (chars[i] ^ chars[31 - i]);
//			chars[i] = (char) (chars[i] ^ chars[31 - i]);
//		}
//		if (chars[0] == '1') { // 负数
//			for (int i = 0; i < 32; i++) {
//				chars[i] = chars[i] == '1' ? '0' : '1'; // 按位取反
//			}
//			return -Integer.parseInt(new String(chars), 2) - 1; // 减1
//		}
//		return Integer.parseInt(new String(chars), 2);
		
		// 更优的解法
		int result = 0;
		for (int i = 0; i < 32; i++) {
			result = result << 1;
			result ^= (n & 1);	//n & 1获取n的最后一位
			n = n >>> 1;
		}
		return result;		
	}
    
    public static void main(String[] args) {
		System.out.println(Integer.toBinaryString(Integer.MAX_VALUE));
		System.out.println(Integer.toBinaryString(Integer.MIN_VALUE));
		System.out.println(Integer.toBinaryString(43261596));
		System.out.println(Integer.toBinaryString(964176192));
		System.out.println(Integer.parseInt("43261596", 2));
		System.out.println(Integer.parseInt("-1", 2));
//		System.out.println(Integer.parseInt("10000000000000000000000000000000", 2));// 抛出异常
		System.out.println(Integer.parseInt("-0000000000000000000000000000011", 2));
	}
    
    /**
     * 191. 位1的个数
     * 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
	 *
	 *	示例 :
	 *	输入: 11
	 *	输出: 3
	 *	解释: 整数 11 的二进制表示为 00000000000000000000000000001011
		
	 *	示例 2:
	 *	输入: 128
	 *	输出: 1
	 *	解释: 整数 128 的二进制表示为 00000000000000000000000010000000
	 *
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
//    	if (n < 0) {
//			n = -n;
//		}
//		int sum = 0;
//		while (n > 0) {
//			sum += n & 1;
//			n  = n >> 1;
//		}
//		return sum;
		int cnt = 0;
		while (n != 0) {
			n = n & (n - 1); // 每次操作都是从后面消除第一个1
			cnt++;
		}
		return cnt;
    }
    
}
